package 数据结构考纲.查找;

public class Find {
    //二分搜索
    public static int bin_search(int[] a, int x) {
        //在查找失败的情况下，l始终处于在此插入x并使得序列有序的位置
        int l = 0, r = a.length - 1;
        int mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (a[mid] == x)
                return mid;
            else if (a[mid] > x)
                r = mid - 1;
            else
                l = mid + 1;
        }
        System.out.println("a[l] = " + a[l]);
        System.out.println("a[r] = " + a[r]);
        return -1;
    }

    public static void main(String[] args) {
        int[] a1 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] a2 = new int[]{1, 2, 3, 5, 6, 7, 8, 9};
        int[] a3 = new int[]{1, 2, 3, 4, 6, 7, 8, 9};

        Find.bin_search(a1, 4);
        Find.bin_search(a2, 4);
        Find.bin_search(a3, 10);
    }

}
